package top.datacluster.basic.algorithm.leetcode.recall;

import java.util.ArrayList;
import java.util.List;

public class LeetCode1499 {



    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0;i < nums.length; i++){

            List<List<Integer>> middle = new ArrayList<>();
            for (int j = 0; j < result.size(); j++){
                List<Integer> temp = new ArrayList<>();
                temp.addAll(result.get(j));
                temp.add(nums[i]);
                middle.add(temp);
            }
            result.addAll(middle);
            List<Integer> value = new ArrayList<>();
            value.add(nums[i]);
            result.add(value);
        }
        result.add(new ArrayList<>());
        return result;
    }

    public List<List<Integer>> subsets1(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        int bmp = (int) Math.pow(2, nums.length);
        // 从 nums.length 个 0 遍历到 nums.length 个 1
        for (int i = 0; i < bmp; i++) {
            List<Integer> subset = new ArrayList<>();
            for (int j = 0; j < nums.length; j++)
                // 将每一位右移最低位，检测其是否为1
                if ((i >>> j & 1) == 1)
                    subset.add(nums[j]);
            subsets.add(subset);
        }
        return subsets;
    }

    public static void main(String[] args) {
        int[] test = new int[]{1,2,3};
        System.out.println(new LeetCode1499().subsets1(test));
    }

}
